# 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 
# 
#  你可以假设数组是非空的，并且给定的数组总是存在多数元素。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：[3,2,3]
# 输出：3 
# 
#  示例 2： 
# 
#  
# 输入：[2,2,1,1,1,2,2]
# 输出：2
#  
# 
#  
# 
#  进阶： 
# 
#  
#  尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。 
#  
#  Related Topics 位运算 数组 分治算法 
#  👍 964 👎 0
import collections
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def major_element_rec(low, high):
            if low == high:
                return nums[low]
            mid = (high - low) // 2 + low
            left_val = major_element_rec(low, mid)
            right_val = major_element_rec(mid + 1, high)
            if left_val == right_val:
                return left_val
            left_count = sum(1 for i in range(low, high+1) if nums[i] == left_val)
            right_count = sum(1 for i in range(low, high+1) if nums[i] == right_val)
            return left_val if left_count > right_count else right_val

        return major_element_rec(0, len(nums) - 1)


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 1. hashset: 储存元素出现的次数, 循环set
#     def majorityElement(self, nums: List[int]) -> int:
#         # num : 次数
#         d = {}
#         for num in nums:
#             if num in d:
#                 d[num] = d[num] + 1
#             else:
#                 d[num] = 1
#         for k, v in d.items():
#             if v > len(nums) / 2:
#                 return k
# 也可以这么写
# def majorityElement(self, nums: List[int]) -> int:
#     # count 是个对象
#     counts = collections.Counter(nums)
#     对counts的key排序, 按值排序, 取最大的key
#     return max(counts.keys(), key=counts.get)
# 2. 排序 大于n/2
#    | 大于情况
# {0,1,2,3}
# 小于 |  都取n/2即可
#      | 大于
# {0,1,2,3,4}
# 小于 |  都取n/2即可
#
#     nums.sort()
#     return nums[len(nums) // 2]

# 分治: 仅作为一个思路, 不够好
# 只有一个元素, 返回该元素; 分为左右, 左右出现众数相等, 则返回; 否则,分别统计左右的值在整个区间出现的次数
#     def majorityElement(self, nums: List[int]) -> int:
#         def major_element_rec(low, high):
#             if low == high:
#                 return nums[low]
#             # 中间下标
#             mid = (high - low) // 2 + low
#             left_val = major_element_rec(low, mid)
#             right_val = major_element_rec(mid + 1, high)
#             if left_val == right_val:
#                 return left_val
#             left_count = sum(1 for i in range(low, high + 1) if nums[i] == left_val)
#             right_count = sum(1 for i in range(low, high + 1) if nums[i] == right_val)
#             return left_val if left_count > right_count else right_val
#
#         return major_element_rec(0, len(nums) - 1)

if __name__ == '__main__':
    s = Solution()
    n = [2, 2, 1, 1, 1, 2, 2]
    result = s.majorityElement(n)
    assert result == 2, result
    n2 = [2, 2]
    result2 = s.majorityElement(n2)
    assert result == 2, result2
